package com.example.demo.leetcode.zuocheng.graph;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.UUID;

/**
 *
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/10 11:16
 */
public class 最小生成树_Prim {




    public static List<Edge> prim(int [][] arr){

        HashMap<String,Node> map = new HashMap<>();

        //将最小生成树转换成基础结构

        for(int i =0 ;i<arr.length;i++){

            int [] temp=arr[i];

            Node from = map.get(temp[1]+"") == null ?  new Node(temp[1]+"") : map.get(temp[1]+"");
            Node to = map.get(temp[2]+"") == null ?  new Node(temp[2]+"") : map.get(temp[2]+"");
            from.out++;
            to.in++;

            Edge edge = new Edge(temp[0],from,to);

            from.edges.add(edge);
            from.nexsts.add(to);

            // queue.add(edge);
            map.put(from.value,from);
            map.put(to.value,to);
        }

        PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        Set<Node> set = new HashSet<>();
        List<Edge> result = new ArrayList<>();

        for(Map.Entry<String,Node> entry : map.entrySet()){
            Node value = entry.getValue();
            if(!set.contains(value)){
                set.add(value);
                for(Edge temp : value.edges){
                    queue.add(temp);
                }
                while(!queue.isEmpty()){
                    Edge edge = queue.poll();
                    Node to = edge.to;
                    if(!set.contains(to)){
                        set.add(to);
                        result.add(edge);
                        for(Edge temp : to.edges){
                            queue.add(temp);
                        }
                    }
                }

            }

        }

        // 采用交并集
        return result;
    }




    public static void main(String[] args) {
        int [][] arr ={{10,1,2},{11,2,3},{12,3,4},{14,4,1},{15,2,1}};
        List<Edge> kruskal = prim(arr);
        for(Edge edge : kruskal){
            System.out.println(edge.weight + ":"+edge.from.value+":"+edge.to.value);
        }
    }


}
